from typing import *
from math import inf
import heapq


class Solution:

    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        array = mat
        m, n = len(array), len(array[0])
        q = []
        ans = [[inf] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if array[i][j] == 0:
                    ans[i][j] = 0
                    heapq.heappush(q, (0, i, j))
        while q:
            d, x, y = heapq.heappop(q)
            for dx, dy in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
                nx, ny = x + dx, y + dy
                if nx >= 0 and nx < m and ny >= 0 and ny < n and ans[nx][ny] == inf:
                    ans[nx][ny] = d + 1
                    heapq.heappush(q,(d + 1, nx, ny))
        return ans

x = y = 0
m = n = 0
for dx,dy in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
    nx,ny=x+dx,y+dy
    if nx >=0 and nx < m and ny>=0 and ny<n:
        pass